home *** CD-ROM | disk | FTP | other *** search
/ BBS in a Box 12 / BBS in a box XII-2.iso / Files II / Prog / B-C / B-YACC.sit / berkeley-yacc-mpw / lalr.c / lalr.c
Encoding:
C/C++ Source or Header  |  1991-10-15  |  11.9 KB  |  679 lines  |  [TEXT/MPS ]
  1. /*
  2.  * Copyright (c) 1989 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Robert Paul Corbett.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #ifndef lint
  38. static char sccsid[] = "@(#)lalr.c    5.3 (Berkeley) 6/1/90";
  39. #endif /* not lint */
  40.  
  41. #include "defs.h"
  42.  
  43. typedef
  44.   struct shorts
  45.     {
  46.       struct shorts *next;
  47.       short value;
  48.     }
  49.   shorts;
  50.  
  51. int tokensetsize;
  52. short *lookaheads;
  53. short *LAruleno;
  54. unsigned *LA;
  55. short *accessing_symbol;
  56. core **state_table;
  57. shifts **shift_table;
  58. reductions **reduction_table;
  59. short *goto_map;
  60. short *from_state;
  61. short *to_state;
  62.  
  63. short **transpose();
  64.  
  65. static int infinity;
  66. static int maxrhs;
  67. static int ngotos;
  68. static unsigned *F;
  69. static short **includes;
  70. static shorts **lookback;
  71. static short **R;
  72. static short *INDEX;
  73. static short *VERTICES;
  74. static int top;
  75.  
  76.  
  77. lalr()
  78. {
  79.     tokensetsize = WORDSIZE(ntokens);
  80.  
  81.     set_state_table();
  82.     set_accessing_symbol();
  83.     set_shift_table();
  84.     set_reduction_table();
  85.     set_maxrhs();
  86.     initialize_LA();
  87.     set_goto_map();
  88.     initialize_F();
  89.     build_relations();
  90.     compute_FOLLOWS();
  91.     compute_lookaheads();
  92. }
  93.  
  94.  
  95.  
  96. set_state_table()
  97. {
  98.     register core *sp;
  99.  
  100.     state_table = NEW2(nstates, core *);
  101.     for (sp = first_state; sp; sp = sp->next)
  102.     state_table[sp->number] = sp;
  103. }
  104.  
  105.  
  106.  
  107. set_accessing_symbol()
  108. {
  109.     register core *sp;
  110.  
  111.     accessing_symbol = NEW2(nstates, short);
  112.     for (sp = first_state; sp; sp = sp->next)
  113.     accessing_symbol[sp->number] = sp->accessing_symbol;
  114. }
  115.  
  116.  
  117.  
  118. set_shift_table()
  119. {
  120.     register shifts *sp;
  121.  
  122.     shift_table = NEW2(nstates, shifts *);
  123.     for (sp = first_shift; sp; sp = sp->next)
  124.     shift_table[sp->number] = sp;
  125. }
  126.  
  127.  
  128.  
  129. set_reduction_table()
  130. {
  131.     register reductions *rp;
  132.  
  133.     reduction_table = NEW2(nstates, reductions *);
  134.     for (rp = first_reduction; rp; rp = rp->next)
  135.     reduction_table[rp->number] = rp;
  136. }
  137.  
  138.  
  139.  
  140. set_maxrhs()
  141. {
  142.   register short *itemp;
  143.   register short *item_end;
  144.   register int length;
  145.   register int max;
  146.  
  147.   length = 0;
  148.   max = 0;
  149.   item_end = ritem + nitems;
  150.   for (itemp = ritem; itemp < item_end; itemp++)
  151.     {
  152.       if (*itemp >= 0)
  153.     {
  154.       length++;
  155.     }
  156.       else
  157.     {
  158.       if (length > max) max = length;
  159.       length = 0;
  160.     }
  161.     }
  162.  
  163.   maxrhs = max;
  164. }
  165.  
  166.  
  167.  
  168. initialize_LA()
  169. {
  170.   register int i, j, k;
  171.   register reductions *rp;
  172.  
  173.   lookaheads = NEW2(nstates + 1, short);
  174.  
  175.   k = 0;
  176.   for (i = 0; i < nstates; i++)
  177.     {
  178.       lookaheads[i] = k;
  179.       rp = reduction_table[i];
  180.       if (rp)
  181.     k += rp->nreds;
  182.     }
  183.   lookaheads[nstates] = k;
  184.  
  185.   LA = NEW2(k * tokensetsize, unsigned);
  186.   LAruleno = NEW2(k, short);
  187.   lookback = NEW2(k, shorts *);
  188.  
  189.   k = 0;
  190.   for (i = 0; i < nstates; i++)
  191.     {
  192.       rp = reduction_table[i];
  193.       if (rp)
  194.     {
  195.       for (j = 0; j < rp->nreds; j++)
  196.         {
  197.           LAruleno[k] = rp->rules[j];
  198.           k++;
  199.         }
  200.     }
  201.     }
  202. }
  203.  
  204.  
  205. set_goto_map()
  206. {
  207.   register shifts *sp;
  208.   register int i;
  209.   register int symbol;
  210.   register int k;
  211.   register short *temp_map;
  212.   register int state2;
  213.   register int state1;
  214.  
  215.   goto_map = NEW2(nvars + 1, short) - ntokens;
  216.   temp_map = NEW2(nvars + 1, short) - ntokens;
  217.  
  218.   ngotos = 0;
  219.   for (sp = first_shift; sp; sp = sp->next)
  220.     {
  221.       for (i = sp->nshifts - 1; i >= 0; i--)
  222.     {
  223.       symbol = accessing_symbol[sp->shift[i]];
  224.  
  225.       if (ISTOKEN(symbol)) break;
  226.  
  227.       if (ngotos == MAXSHORT)
  228.         fatal("too many gotos");
  229.  
  230.       ngotos++;
  231.       goto_map[symbol]++;
  232.         }
  233.     }
  234.  
  235.   k = 0;
  236.   for (i = ntokens; i < nsyms; i++)
  237.     {
  238.       temp_map[i] = k;
  239.       k += goto_map[i];
  240.     }
  241.  
  242.   for (i = ntokens; i < nsyms; i++)
  243.     goto_map[i] = temp_map[i];
  244.  
  245.   goto_map[nsyms] = ngotos;
  246.   temp_map[nsyms] = ngotos;
  247.  
  248.   from_state = NEW2(ngotos, short);
  249.   to_state = NEW2(ngotos, short);
  250.  
  251.   for (sp = first_shift; sp; sp = sp->next)
  252.     {
  253.       state1 = sp->number;
  254.       for (i = sp->nshifts - 1; i >= 0; i--)
  255.     {
  256.       state2 = sp->shift[i];
  257.       symbol = accessing_symbol[state2];
  258.  
  259.       if (ISTOKEN(symbol)) break;
  260.  
  261.       k = temp_map[symbol]++;
  262.       from_state[k] = state1;
  263.       to_state[k] = state2;
  264.     }
  265.     }
  266.  
  267.   FREE(temp_map + ntokens);
  268. }
  269.  
  270.  
  271.  
  272. /*  Map_goto maps a state/symbol pair into its numeric representation.    */
  273.  
  274. int
  275. map_goto(state, symbol)
  276. int state;
  277. int symbol;
  278. {
  279.     register int high;
  280.     register int low;
  281.     register int middle;
  282.     register int s;
  283.  
  284.     low = goto_map[symbol];
  285.     high = goto_map[symbol + 1];
  286.  
  287.     for (;;)
  288.     {
  289.     assert(low <= high);
  290.     middle = (low + high) >> 1;
  291.     s = from_state[middle];
  292.     if (s == state)
  293.         return (middle);
  294.     else if (s < state)
  295.         low = middle + 1;
  296.     else
  297.         high = middle - 1;
  298.     }
  299. }
  300.  
  301.  
  302.  
  303. initialize_F()
  304. {
  305.   register int i;
  306.   register int j;
  307.   register int k;
  308.   register shifts *sp;
  309.   register short *edge;
  310.   register unsigned *rowp;
  311.   register short *rp;
  312.   register short **reads;
  313.   register int nedges;
  314.   register int stateno;
  315.   register int symbol;
  316.   register int nwords;
  317.  
  318.   nwords = ngotos * tokensetsize;
  319.   F = NEW2(nwords, unsigned);
  320.  
  321.   reads = NEW2(ngotos, short *);
  322.   edge = NEW2(ngotos + 1, short);
  323.   nedges = 0;
  324.  
  325.   rowp = F;
  326.   for (i = 0; i < ngotos; i++)
  327.     {
  328.       stateno = to_state[i];
  329.       sp = shift_table[stateno];
  330.  
  331.       if (sp)
  332.     {
  333.       k = sp->nshifts;
  334.  
  335.       for (j = 0; j < k; j++)
  336.         {
  337.           symbol = accessing_symbol[sp->shift[j]];
  338.           if (ISVAR(symbol))
  339.         break;
  340.           SETBIT(rowp, symbol);
  341.         }
  342.  
  343.       for (; j < k; j++)
  344.         {
  345.           symbol = accessing_symbol[sp->shift[j]];
  346.           if (nullable[symbol])
  347.         edge[nedges++] = map_goto(stateno, symbol);
  348.         }
  349.     
  350.       if (nedges)
  351.         {
  352.           reads[i] = rp = NEW2(nedges + 1, short);
  353.  
  354.           for (j = 0; j < nedges; j++)
  355.         rp[j] = edge[j];
  356.  
  357.           rp[nedges] = -1;
  358.           nedges = 0;
  359.         }
  360.     }
  361.  
  362.       rowp += tokensetsize;
  363.     }
  364.  
  365.   SETBIT(F, 0);
  366.   digraph(reads);
  367.  
  368.   for (i = 0; i < ngotos; i++)
  369.     {
  370.       if (reads[i])
  371.     FREE(reads[i]);
  372.     }
  373.  
  374.   FREE(reads);
  375.   FREE(edge);
  376. }
  377.  
  378.  
  379.  
  380. build_relations()
  381. {
  382.   register int i;
  383.   register int j;
  384.   register int k;
  385.   register short *rulep;
  386.   register short *rp;
  387.   register shifts *sp;
  388.   register int length;
  389.   register int nedges;
  390.   register int done;
  391.   register int state1;
  392.   register int stateno;
  393.   register int symbol1;
  394.   register int symbol2;
  395.   register short *shortp;
  396.   register short *edge;
  397.   register short *states;
  398.   register short **new_includes;
  399.  
  400.   includes = NEW2(ngotos, short *);
  401.   edge = NEW2(ngotos + 1, short);
  402.   states = NEW2(maxrhs + 1, short);
  403.  
  404.   for (i = 0; i < ngotos; i++)
  405.     {
  406.       nedges = 0;
  407.       state1 = from_state[i];
  408.       symbol1 = accessing_symbol[to_state[i]];
  409.  
  410.       for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
  411.     {
  412.       length = 1;
  413.       states[0] = state1;
  414.       stateno = state1;
  415.  
  416.       for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
  417.         {
  418.           symbol2 = *rp;
  419.           sp = shift_table[stateno];
  420.           k = sp->nshifts;
  421.  
  422.           for (j = 0; j < k; j++)
  423.         {
  424.           stateno = sp->shift[j];
  425.           if (accessing_symbol[stateno] == symbol2) break;
  426.         }
  427.  
  428.           states[length++] = stateno;
  429.         }
  430.  
  431.       add_lookback_edge(stateno, *rulep, i);
  432.  
  433.       length--;
  434.       done = 0;
  435.       while (!done)
  436.         {
  437.           done = 1;
  438.           rp--;
  439.           if (ISVAR(*rp))
  440.         {
  441.           stateno = states[--length];
  442.           edge[nedges++] = map_goto(stateno, *rp);
  443.           if (nullable[*rp] && length > 0) done = 0;
  444.         }
  445.         }
  446.     }
  447.  
  448.       if (nedges)
  449.     {
  450.       includes[i] = shortp = NEW2(nedges + 1, short);
  451.       for (j = 0; j < nedges; j++)
  452.         shortp[j] = edge[j];
  453.       shortp[nedges] = -1;
  454.     }
  455.     }
  456.  
  457.   new_includes = transpose(includes, ngotos);
  458.  
  459.   for (i = 0; i < ngotos; i++)
  460.     if (includes[i])
  461.       FREE(includes[i]);
  462.  
  463.   FREE(includes);
  464.  
  465.   includes = new_includes;
  466.  
  467.   FREE(edge);
  468.   FREE(states);
  469. }
  470.  
  471.  
  472. add_lookback_edge(stateno, ruleno, gotono)
  473. int stateno, ruleno, gotono;
  474. {
  475.     register int i, k;
  476.     register int found;
  477.     register shorts *sp;
  478.  
  479.     i = lookaheads[stateno];
  480.     k = lookaheads[stateno + 1];
  481.     found = 0;
  482.     while (!found && i < k)
  483.     {
  484.     if (LAruleno[i] == ruleno)
  485.         found = 1;
  486.     else
  487.         ++i;
  488.     }
  489.     assert(found);
  490.  
  491.     sp = NEW(shorts);
  492.     sp->next = lookback[i];
  493.     sp->value = gotono;
  494.     lookback[i] = sp;
  495. }
  496.  
  497.  
  498.  
  499. short **
  500. transpose(R, n)
  501. short **R;
  502. int n;
  503. {
  504.   register short **new_R;
  505.   register short **temp_R;
  506.   register short *nedges;
  507.   register short *sp;
  508.   register int i;
  509.   register int k;
  510.  
  511.   nedges = NEW2(n, short);
  512.  
  513.   for (i = 0; i < n; i++)
  514.     {
  515.       sp = R[i];
  516.       if (sp)
  517.     {
  518.       while (*sp >= 0)
  519.         nedges[*sp++]++;
  520.     }
  521.     }
  522.  
  523.   new_R = NEW2(n, short *);
  524.   temp_R = NEW2(n, short *);
  525.  
  526.   for (i = 0; i < n; i++)
  527.     {
  528.       k = nedges[i];
  529.       if (k > 0)
  530.     {
  531.       sp = NEW2(k + 1, short);
  532.       new_R[i] = sp;
  533.       temp_R[i] = sp;
  534.       sp[k] = -1;
  535.     }
  536.     }
  537.  
  538.   FREE(nedges);
  539.  
  540.   for (i = 0; i < n; i++)
  541.     {
  542.       sp = R[i];
  543.       if (sp)
  544.     {
  545.       while (*sp >= 0)
  546.         *temp_R[*sp++]++ = i;
  547.     }
  548.     }
  549.  
  550.   FREE(temp_R);
  551.  
  552.   return (new_R);
  553. }
  554.  
  555.  
  556.  
  557. compute_FOLLOWS()
  558. {
  559.   digraph(includes);
  560. }
  561.  
  562.  
  563. compute_lookaheads()
  564. {
  565.   register int i, n;
  566.   register unsigned *fp1, *fp2, *fp3;
  567.   register shorts *sp, *next;
  568.   register unsigned *rowp;
  569.  
  570.   rowp = LA;
  571.   n = lookaheads[nstates];
  572.   for (i = 0; i < n; i++)
  573.     {
  574.       fp3 = rowp + tokensetsize;
  575.       for (sp = lookback[i]; sp; sp = sp->next)
  576.     {
  577.       fp1 = rowp;
  578.       fp2 = F + tokensetsize * sp->value;
  579.       while (fp1 < fp3)
  580.         *fp1++ |= *fp2++;
  581.     }
  582.       rowp = fp3;
  583.     }
  584.  
  585.   for (i = 0; i < n; i++)
  586.     for (sp = lookback[i]; sp; sp = next)
  587.       {
  588.         next = sp->next;
  589.         FREE(sp);
  590.       }
  591.  
  592.   FREE(lookback);
  593.   FREE(F);
  594. }
  595.  
  596.  
  597. digraph(relation)
  598. short **relation;
  599. {
  600.   register int i;
  601.  
  602.   infinity = ngotos + 2;
  603.   INDEX = NEW2(ngotos + 1, short);
  604.   VERTICES = NEW2(ngotos + 1, short);
  605.   top = 0;
  606.  
  607.   R = relation;
  608.  
  609.   for (i = 0; i < ngotos; i++)
  610.     INDEX[i] = 0;
  611.  
  612.   for (i = 0; i < ngotos; i++)
  613.     {
  614.       if (INDEX[i] == 0 && R[i])
  615.     traverse(i);
  616.     }
  617.  
  618.   FREE(INDEX);
  619.   FREE(VERTICES);
  620. }
  621.  
  622.  
  623.  
  624. traverse(i)
  625. register int i;
  626. {
  627.   register unsigned *fp1;
  628.   register unsigned *fp2;
  629.   register unsigned *fp3;
  630.   register int j;
  631.   register short *rp;
  632.  
  633.   int height;
  634.   unsigned *base;
  635.  
  636.   VERTICES[++top] = i;
  637.   INDEX[i] = height = top;
  638.  
  639.   base = F + i * tokensetsize;
  640.   fp3 = base + tokensetsize;
  641.  
  642.   rp = R[i];
  643.   if (rp)
  644.     {
  645.       while ((j = *rp++) >= 0)
  646.     {
  647.       if (INDEX[j] == 0)
  648.         traverse(j);
  649.  
  650.       if (INDEX[i] > INDEX[j])
  651.         INDEX[i] = INDEX[j];
  652.  
  653.       fp1 = base;
  654.       fp2 = F + j * tokensetsize;
  655.  
  656.       while (fp1 < fp3)
  657.         *fp1++ |= *fp2++;
  658.     }
  659.     }
  660.  
  661.   if (INDEX[i] == height)
  662.     {
  663.       for (;;)
  664.     {
  665.       j = VERTICES[top--];
  666.       INDEX[j] = infinity;
  667.  
  668.       if (i == j)
  669.         break;
  670.  
  671.       fp1 = base;
  672.       fp2 = F + j * tokensetsize;
  673.  
  674.       while (fp1 < fp3)
  675.         *fp2++ = *fp1++;
  676.     }
  677.     }
  678. }
  679.